package priority_queue;

public class MaxPriorityQueue {
    private int queueSize;
    private int[] queue;

    public MaxPriorityQueue(int[] queue) {
        this.queue = queue;
        queueSize = queue.length;
        buildMaxHeap();
    }

    private void maxHeapify(int cur) {
        int left = (cur << 1) + 1;    //左孩子结点 2n+1
        int right = (cur << 1) + 2;    //右孩子结点 2n+2
        int largest = cur;
        if (left < queueSize && queue[left] > queue[largest]) {
            largest = left;
        }
        if (right < queueSize && queue[right] > queue[largest]) {
            largest = right;
        }
        if (largest != cur) {
            int temp = queue[cur];
            queue[cur] = queue[largest];
            queue[largest] = temp;
            maxHeapify(largest);
        }
    }

    private void buildMaxHeap() {
        for (int i = queueSize / 2 + 1; i >= 0; i--) {
            maxHeapify(i);
        }
    }

    public int queueMaximum() {
        return queue[0];
    }

    public int queueExtractMaximum() {
        if (queueSize < 1) {
            return -1;
        }
        int maximum = queue[0];
        queue[0] = queue[queueSize - 1];
        queueSize--;
        maxHeapify(0);
        return maximum;
    }

    public void queueIncreaseKey(int idx, int key) {
        if (queue[idx] > key) {
            return;
        }
        queue[idx] = key;
        while (idx > 0 && queue[(idx - 1) >> 1] < queue[idx]) {
            int temp = queue[idx];
            queue[idx] = queue[(idx - 1) >> 1];
            queue[(idx - 1) >> 1] = temp;
            idx = (idx - 1) >> 1;
        }
    }

    public void queueInsertKey(int key) {
        if (queueSize == queue.length) {
            int[] oldQueue = queue;
            int[] newQueue = new int[queue.length * 2];
            System.arraycopy(oldQueue, 0, newQueue, 0, oldQueue.length);
            queue = newQueue;
        }
        queueSize++;
        queue[queueSize - 1] = Integer.MIN_VALUE;
        queueIncreaseKey(queueSize - 1, key);
    }

    public void displayMaxQueue() {
        System.out.println("根 左 右");
        for (int i = 0; i < queueSize; i++) {
            System.out.print(queue[i]);
            int l = (i << 1) + 1;
            int r = (i << 1) + 2;
            if (l < queueSize) {
                System.out.print(" " + queue[l]);
            }
            if (r < queueSize) {
                System.out.print(" " + queue[r]);
            }
            System.out.println();
        }
    }
}
